#include <stdio.h>
#include "single_linked_list.cpp"

// 将带头结点的链表就地逆置
void Reverse(LinkedList &L)
{
    LNode *pre = NULL;    // 前驱结点
    LNode *cur = L->next; // 当前结点
    LNode *next;          // 后继结点
    while (cur != NULL)
    {
        next = cur->next; // next记录当前结点的后继 防止断链
        cur->next = pre;  // 当前结点反向
        pre = cur;        // 下一次循环
        cur = next;
    }
    L->next = pre;
}

// 递归 不带头结点
LinkedList Reverse2(LinkedList &L) {
    if (L->next == NULL) {
        return L;
    }
    // 遍历到链表尾部 
    LNode *newHead = Reverse2(L->next);
    // 反转
    L->next->next = L;
    // 断链
    L->next = NULL;
 
    return newHead;
}

// 带头结点 递归
void Reverse3(LinkedList &L) {
    LNode *res = Reverse2(L->next);
    L->next = res;
}


int main()
{
    LinkedList L;
    InitList(L);

    // 插入
    ListAppend(L, 2);
    ListAppend(L, 5);
    ListAppend(L, 9);
    ListAppend(L, 7);
    ListAppend(L, 3);
    ListAppend(L, 6);
    PrintList(L);

    Reverse(L);
    PrintList(L);

    Reverse3(L);
    PrintList(L);

    return 0;
}